The present invention is directed to apparatus and methods for path identification in a communication network and, in particular, to apparatus and methods for identifying the route followed between a source unit and a destination unit through a data communication network.
A communication network includes multiple network elements which are connected together into a single entity by a set of links. Each link joins together two distinct network elements. The network allows end-user data to be transmitted to a network element. The data is then transferred across the network, through a subset of the links and network elements, and is regenerated at another network element.
The network provides one or more levels of service for the end-user data which is carried over same. These levels of service may be dictated by the needs of the end-user. The level of service may also control the amount of data which can be transferred by the end-user, the speed at which the data passes through the network, and the probability that the data will be discarded by the network during transfer.
In creating and maintaining a communication network, it is necessary for the network operator to be able to ensure that end-user data is being communicated across the network in the intended manner. This requires that the network operator be able to accurately identify how the network elements are connected to one another as well as to ascertain the identity of the path which the end-user data follows as it passes through the network. Without this capability, the network operator cannot be certain that end-user data is being received by, and only by, the intended recipient(s) of that data. Further, there should be assurance that the data is being transferred at the desired service quality which is requested by the end-user.
One approach to solving this problem is to query the network""s configuration management system so as to identify the path which the end-user data has been instructed to follow through the network. The information in the configuration management system, however, may not necessarily reflect what is actually happening within the network. As a result, it is entirely possible that end-user data may flow in a different manner than that intended by the configuration management system.
Problems of the above nature may arise as the result of hardware problems which may arise within the network, software problems which may arise within the network, or those problems which may arise through human error. In this regard, apparatus and methods are needed, for determining network configuration as well as path identification in a communication network, which overcome the shortfalls associated with existing systems.
The present invention provides apparatus and methods for identifying the path of connections through, and the topology of, a communication network or a data network. The present invention accomplishes path identification by injecting management data traffic into the connection at any network element or node along the path. The present invention may be utilized in asynchronous transfer mode (ATM) systems, packet switched networks and other communication networks.
The apparatus includes a source unit, a plurality of network elements or nodes, a network management element and a destination unit. The network elements or nodes may be linked to adjacent network elements by any one or more of wire links, wireless links, optical communication links, satellite links, analog communication links, digital communication links, personal communication services links, etc. The network elements may be linked to the components of the apparatus or network via any suitable communication medium. The network elements may be linked together in any contiguous network topology, including a complete or incomplete mesh, star, ring, line, or other type of configuration. The network elements are controlled or managed by the network management element which may control or manage any number, or group, of network elements.
In the apparatus, the source unit communicates with the destination unit via the network of network elements. The communication between the source unit and the destination unit is provided through a connection through the network elements. The data flow between the source unit and the destination unit is bi-directional so as to facilitate communication between the source unit and the destination unit and vice versa.
The direction of the data flow between the source unit and the destination unit is defined as the xe2x80x9cforwardxe2x80x9d direction, while the direction of the data flow between the destination unit and the source unit is defined as the xe2x80x9cbackwardxe2x80x9d direction.
The network elements are also operatively connected to the network management element. The network management element provides command and control signals to the network elements so as to control and/or monitor the operation of same when, and if, desired.
The network elements may include a central processing unit (CPU) and an associated memory storage device. The CPU of the network element performs various processing routines during apparatus operation. The network element also includes a receiver, a transmitter and a data storage element. The network element also includes a data routing device.
The receiver receives data from the network along one or more links. The data router routes the data to the transmitter, or to the CPU, or both, in accordance with the intended destination, or the intended use, for the data. The transmitter may transmit data to the network along one or more links. Data may also be temporarily stored in the data storage device during operation of the network element.
The present invention injects control data into the data which is communicated over the apparatus or network. The CPU of the network element generates control data and injects this control data into the data which is being transmitted through the apparatus or network.
Each of the network elements or nodes has assigned thereto a unique node identification code. These node identification codes serve to identify the network element.
The present invention provides apparatus and methods for identifying the path through a communication network as well as the distances between the respective network elements or nodes. A node, defined as a xe2x80x9ctrace request nodexe2x80x9d, transmits control data streams to all of the remaining nodes in the network which are defined as xe2x80x9cresponder nodesxe2x80x9d.
The apparatus and methods of the present invention may utilize a multi-stage, control data generation and processing routine which is performed for each linked portion of the network relative to the trace request node. The data or signals may be transmitted in directions away from the trace request node. The portions of the network, which are connected to the node, may be processed independently of one another.
In a first stage of operation, the trace request node may transmit a first control data stream into each of the portions of the network, along the connection to be traced. In a second stage of operation, a second control data stream may be added by any of the responder nodes, intermediate or otherwise. The data from both of these control data streams may then be utilized by other responder nodes in order to gather connection information and topology information, as well as intermediate data, which is related to the distances of each of the responder nodes from the trace request node.
In a third stage of processing, the trace request node may transmit a third control data stream, which contains additional management data, into the network portions, thereby triggering the return of fourth control data stream responses from the responder nodes to the trace request node. These returned fourth control data streams, which may constitute a fourth stage of processing, contain distance information which is representative of the distance of each of the respective responder nodes from the trace request node. The distance information, as well as the other obtained information, may thereafter be utilized by the trace request node for analysis and/or display purposes. In this manner, information regarding network topology, as well as distance data, may be obtained.
The control data streams, which may be generated by the respective nodes during apparatus operation, may consist of data which is unique to the processing routine. The control data stream may contain a command code which identifies the type of operation to be carried out by the network nodes, a source identification code (source ID) which identifies the trace request node, and a correlation tag which is unique to the trace request and unique to the portion of the network being interrogated. The control data stream may also contain a responder identification code (responder ID) which, once inserted by a respective responder node, identifies the responder node, and a distance count which indicates how far the responder node is located from the trace request node.
The CPUs of each of the nodes may be capable of performing all of the processing operations described herein, so that any one of the nodes may function as a trace request node or as a responder node at any given time.
The network management element may control the issuance of the trace request operations and the trace request nodes which issue same. The results of apparatus operation may also be obtained at the network management element.
The apparatus and methods of the present invention may perform processing operations in a single direction only, as well as in multiple directions.
In another embodiment of the present invention, the trace request node may perform a second trace request sequence of operations following a conclusion of a trace sequence. The results of the two sequences may then be compared in order to verify that they are the same. If the results fail to match, the trace request node may continue to perform additional trace request sequences until matching results are obtained for two successive sequences.
In yet another embodiment of the present invention, the trace data streams may be transmitted by responder nodes in the direction opposite the direction from which the trace request data stream was received. Such an embodiment may facilitate the detection of situations in which the trace report data streams provide the trace request node with incorrect or incomplete results, resulting from the corruption, or loss, of trace-related data streams within the apparatus. The operation of the trace request node may be modified so that it may account for instances in which the distance values, which are computed by the responder nodes, may be reversed.
In still another alternate embodiment of the present invention, each responder node may record the arrival time of the trace data stream and automatically return a trace response data stream upon the expiration of a pre-specified time period. In this embodiment, the apparatus may serve to prevent errors which may result from the corruption or loss of trace related data streams within the apparatus.
In another alternate embodiment, the apparatus and methods of the present invention may operate in a mode such that trace request data streams may overlap with each other while the integrity of the data and results obtained are maintained.
In yet another embodiment of the present invention, trace requests may be performed along connections which have a single source and multiple destinations and vice versa.
In still another embodiment of the present invention, the network elements or nodes may be comprised of two or more separate node elements. Each of the separate node elements may generate trace requests and perform network connection and/or topology processing, as well as distance data determination, for each of the links which link the node to the apparatus or network.
Accordingly, it is an object of the present invention to provide apparatus and methods for determining the configuration and/or topology of a communication network.
It is another object of the present invention to provide apparatus and methods for performing path identification and distance determination in a communication network.
It is yet another object of the present invention to provide a network element or node which may be utilized for determining configuration and/or topology, path identification, and/or distance data, in a communication network.
It is another object of the present invention to provide apparatus and methods for performing path identification in a communication network which may be configured in any topology.
It is yet another object of the present invention to provide apparatus and methods for network configuration and/or topology determination, path identification and/or distance determination in a communication network which utilizes network elements which perform various processing routines.
It is still another object of the present invention to provide apparatus and methods for determining the distances between network elements in a communication network.
It is still another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network, by utilizing network elements which may perform path trace request operations as well as path trace response operations.
It is yet another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network by transmitting trace request messages in both forward and backward directions relative to a requesting network element.
It is another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network by utilizing network elements which operate under software control.
It is still another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, or determining distance between network elements, in a communication network which may perform any of the above operations in any one or more directions relative to a requesting network element.
It is another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network which may perform operational sequences until a satisfactory result is obtained.
It is yet another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network which utilizes network elements which may include multiple processing elements and routines.
It is yet another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network which utilizes network elements which may automatically respond to apparatus operation.
It is yet another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network which utilizes network elements which may perform multiple processing operations simultaneously.
It is yet another object of the present invention to provide apparatus and methods for performing path identification, determining network configuration and/or topology, and/or determining distance between network elements, in a communication network which utilizes network elements which may process multiple processing sequences along connections which have multiple paths.
Other objects and advantages of the present invention will be apparent to one skilled in the art upon a review of the Description of the Preferred Embodiment taken in conjunction with the Drawings which follow.